#include <iostream>
#include <vector>
using namespace std;

class Solution {
	int limit = 0;
	bool can(vector<int> &tk, int status, int elen, int e, vector<int> &dp)
	{
		if (e == 4) {
			return true;
		}

		if(dp[status] != -1){
			return dp[status];
		}

		for (int i = 0; i < tk.size(); i++) {
			if (status & (1 << i)) {
				if (elen + tk[i] < limit && can(tk, status & ~(1 << i), elen + tk[i], e, dp)){
                                        return dp[status] = true;
                                }
                                if( elen + tk[i] == limit && can(tk, status & ~(1 << i), 0, e + 1, dp)){
                                        return dp[status] = true;
                                }
			}
		}
                return dp[status]=false;
	}

    public:
	bool makesquare(vector<int> &matchsticks)
	{
		int sum = 0;
		for (int i = 0; i < matchsticks.size(); i++) {
			sum += matchsticks[i];
		}

		if (sum % 4) {
			return false;
		}

		limit = sum / 4;

		vector<int> dp(1 << matchsticks.size(), -1);
                return can(matchsticks, (1 << matchsticks.size()) - 1, 0, 0, dp);
	}
};

int main()
{
	vector<int> matchsticks = { 3,3,3,3,4 };
	cout << Solution().makesquare(matchsticks) << endl;
	return 0;
}